class Solution {
    public int[] exchange(int[] nums) {
        partition(nums, 0, nums.length - 1);
        return nums;
    }
    public void partition(int[] arr, int i, int j){
        while(i < j){
            // 从右往左找奇数
            while(i < j && (arr[j] % 2 == 0)){
                j--;
            }
            // 从左往右找偶数
            while(i < j && (arr[i] % 2 != 0)){
                i++;
            }
            swap(arr, i, j);
        }
    }
    public void swap(int[] arr, int a, int b){
        int t = arr[a];
        arr[a] = arr[b];
        arr[b] = t;
    }
}